package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 234.回文链表
 *
 * @program: LeetCode->LeetCode_234
 * @description: 234.回文链表
 * @author: cg
 * @create: 2021-08-31 22:18
 **/
public class LeetCode_234 {

    @Test
    public void test234() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1)))));
        ListNode head1 = new ListNode(1, new ListNode(1));
        //System.out.println(isPalindrome(head));
        System.out.println(isPalindrome1(head));
        System.out.println(isPalindrome1(head1));
    }

    /**
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * <p>
     * 示例 1：
     * 输入：head = [1,2,2,1]
     * 输出：true
     * <p>
     * 示例 2：
     * 输入：head = [1,2]
     * 输出：false
     * <p>
     * 提示：
     * 1) 链表中节点数目在范围[1, 105] 内
     * 2) 0 <= Node.val <= 9
     *
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head) {
        //双指针和栈
        if (head == null || head.next == null) {
            return true;
        }
        //如果慢指针先走一步，那么偶数个结点，慢指针则指向中间两个结点的后一个，奇数个结点，慢指针则指向中间结点的后一个
        //如果快指针先走一步或者快慢指针同时开始，那么偶数个结点，慢指针则指向中间两个结点的前一个，奇数个结点，慢指针则指向中间结点的前一个，慢指针就需要再往后走一步再入栈
        ListNode fast = head, slow = head.next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Stack<ListNode> stack = new Stack<>();
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        while (!stack.isEmpty()) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        //快慢指针解决
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head, slow = head;
        //通过快慢指针找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //如果fast不为空，说明链表的长度是奇数个
        if (fast != null) {
            slow = slow.next;
        }
        //反转后半部分链表
        slow = reverse(slow);
        fast = head;
        while (slow != null) {
            //然后比较，判断节点值是否相等
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     * 反转链表
     */
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    /*public boolean isPalindrome(ListNode head) {
        //递归解决
        frontPointer = head;
        return recursivelyCheck(head);
    }
    private ListNode frontPointer;
    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }*/
    /*public boolean isPalindrome(ListNode head) {
        //将值复制到数组中后用双指针法解决
        List<Integer> values = new ArrayList<Integer>();
        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            values.add(currentNode.val);
            currentNode = currentNode.next;
        }
        // 使用双指针判断是否回文
        int front = 0;
        int back = values.size() - 1;
        while (front < back) {
            if (!values.get(front).equals(values.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }*/

}
